package com.lft.sort07.radix_sort;

import java.util.Arrays;

/**
 * 基数排序（桶排序的升级）
 */
public class RadixSort {
	public static void main(String[] args) {
		int[] a = {53, 3, 542, 748, 14, 214};
		System.out.println(Arrays.toString(radixSort(a)));
	}
	
	public static int[] radixSort(int[] a) {
		// 得到原数组中最大的数。
		int max = a[0];
		for (int i = 1; i < a.length; i++) {
			if (max < a[i]) {
				max = a[i];
			}
		}
		// 最大数位数。
		int maxLength = (max + "").length();
		// 创建桶
		int[][] bucket = new int[10][a.length];
		// 计数每个桶中元素的个数。
		int[] bucketElementCounts = new int[10];
		// 临时索引，当往原数组中存放的时候使用，用于标记存放的索引位置。
		int index;
		for (int m = 0, n = 1; m < maxLength; m++, n *= 10) {
			// 按元素的个、十、百、千、万位置上的数，往对应的桶里放。
			for (int i = 0; i < a.length; i++) {
				int digitOfElement = a[i] / n % 10;
				bucket[digitOfElement][bucketElementCounts[digitOfElement]] = a[i];
				bucketElementCounts[digitOfElement]++;
			}
			index = 0;
			// 遍历每个桶
			for (int i = 0; i < bucketElementCounts.length; i++) {
				// 桶中的元素个数大于0的，说明有元素。
				if (bucketElementCounts[i] > 0) {
					// 遍历当前的桶。依次从桶中取出数据，替换掉原数组。
					for (int j = 0; j < bucketElementCounts[i]; j++) {
						a[index++] = bucket[i][j];
					}
				}
				// 每个桶遍历完成之后，要将该桶中的元素个数记录表中的数值，设置为0
				bucketElementCounts[i] = 0;
			}
		}
		return a;
		
		// // 定义一个二维数组，表示 10 个桶，每个桶就是一个一维数组。
		// // 说明：
		// // 1. 二维数组包含10个一维数组。
		// // 2. 为了防止在放入娄的时候，数据溢出，则每个一维数组（桶），大小定义为 arr.length
		// // 3. 基数排序就是使用空间换时间。
		// int[][] bucket = new int[10][a.length];
		//
		// // 为了记录每个桶中，实际存放了多少个数据，定义一个一维数组来记录各个桶每次放入的数据个数。
		// // bucketElementCounts[0] 记录的就是 bucket[0] 桶里放的数据个数
		// int[] bucketElementCounts = new int[10];
		//
		// // 第一轮排序——针对每个元素的个位进行排序。
		// for (int i = 0; i < a.length; i++) {
		// 	// 取出每个元素的个位上的值。
		// 	int digitOfElement = a[i] % 10;
		// 	// 放入到对应的桶中
		// 	bucket[digitOfElement][bucketElementCounts[digitOfElement]] = a[i];
		// 	bucketElementCounts[digitOfElement]++;
		// }
		//
		// // 放完之后，整理放回数组中。
		// int index = 0;
		// // 遍历每一个桶，并将中的数据，放入到原数组中。
		// for (int i = 0; i < bucketElementCounts.length; i++) {
		// 	// 如果桶中有数据，才放入到原数组中。
		// 	if (bucketElementCounts[i] > 0) {
		// 		// 遍历该桶中的数据。放入到原数组中。
		// 		for (int j = 0; j < bucketElementCounts[i]; j++) {
		// 			a[index++] = bucket[i][j];
		// 		}
		// 	}
		// 	// 第 1 轮取出后，要将桶中的元素个数置为0
		// 	bucketElementCounts[i] = 0;
		// }
		//
		// // 第二轮
		// for (int i = 0; i < a.length; i++) {
		// 	// 取出每个元素的十位上的值。
		// 	int digitOfElement = a[i] / 10 % 10;
		// 	// 放入到对应的桶中
		// 	bucket[digitOfElement][bucketElementCounts[digitOfElement]] = a[i];
		// 	bucketElementCounts[digitOfElement]++;
		// }
		//
		// // 放完之后，整理放回数组中。
		// index = 0;
		// // 遍历每一个桶，并将中的数据，放入到原数组中。
		// for (int i = 0; i < bucketElementCounts.length; i++) {
		// 	// 如果桶中有数据，才放入到原数组中。
		// 	if (bucketElementCounts[i] > 0) {
		// 		// 遍历该桶中的数据。放入到原数组中。
		// 		for (int j = 0; j < bucketElementCounts[i]; j++) {
		// 			a[index++] = bucket[i][j];
		// 		}
		// 	}
		// 	// 第 2 轮取出后，要将桶中的元素个数置为0
		// 	bucketElementCounts[i] = 0;
		// }
		//
		// // 第三轮
		// for (int i = 0; i < a.length; i++) {
		// 	// 取出每个元素的百位上的值。
		// 	int digitOfElement = a[i] / 10 / 10 % 10;
		// 	// 放入到对应的桶中
		// 	bucket[digitOfElement][bucketElementCounts[digitOfElement]] = a[i];
		// 	bucketElementCounts[digitOfElement]++;
		// }
		//
		// // 放完之后，整理放回数组中。
		// index = 0;
		// // 遍历每一个桶，并将中的数据，放入到原数组中。
		// for (int i = 0; i < bucketElementCounts.length; i++) {
		// 	// 如果桶中有数据，才放入到原数组中。
		// 	if (bucketElementCounts[i] > 0) {
		// 		// 遍历该桶中的数据。放入到原数组中。
		// 		for (int j = 0; j < bucketElementCounts[i]; j++) {
		// 			a[index++] = bucket[i][j];
		// 		}
		// 	}
		// 	// 第 3 轮取出后，要将桶中的元素个数置为0
		// 	bucketElementCounts[i] = 0;
		// }
		// return a;
	}
}
